package my.algorithm.sort;

import org.apache.commons.lang.ArrayUtils;

/**
 * 冒泡排序
 * @author xsw
 * @date 2018年9月27日
 */
public class BubbleSort {
	public static void main(String[] args) {
		int[] list = { 6, 5, 3, 1, 8, 7, 2, 4 };
		System.out.println(ArrayUtils.toString(list));
		sort(list);
//		sortBetterSign(list);
//		sortBetterIndex(list);
		System.out.println(ArrayUtils.toString(list));
	}
	
	// 分类 -------------- 内部比较排序
	// 数据结构 ---------- 数组
	// 最差时间复杂度 ---- O(n^2)
	// 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
	// 平均时间复杂度 ---- O(n^2)
	// 所需辅助空间 ------ O(1)
	// 稳定性 ------------ 稳定
	public static void sort(int[] list){
		if(list == null || list.length == 0) return ;
		int temp;
		/**
		 * 1. 外层循环n次，代表要找n次最大值（右侧为最大值）
		 * 2. 内层循环n-i-1次，因为右侧已经为排序好的数据
		 */
		for (int i = 0; i < list.length; i++) {
			for (int j = 0; j < list.length - i -1; j++) {
				if(list[j]>list[j+1]){
					temp = list[j];
					list[j] = list[j+1];
					list[j+1] = temp;
				}
			}
			System.out.println(i+"\t"+ArrayUtils.toString(list));
		}
	}
	
	/**
	 * 冒泡排序改进版:添加boolean变量，标记上一次比较是否发生数据交换，如果没有发生数据交换，则认为已经有序，退出排序循环。
	 * @param list
	 */
	public static void sortBetterSign(int[] list){
		if(list == null || list.length == 0) return ;
		int temp;
		/**
		 * 1. 外层循环n次，代表要找n次最大值（右侧为最大值）
		 * 2. 内层循环n-i-1次，因为右侧已经为排序好的数据
		 */
		boolean swap; 
		for (int i = 0; i < list.length; i++) {
			swap = false;
			for (int j = 0; j < list.length - i -1; j++) {
				if(list[j]>list[j+1]){
					temp = list[j];
					list[j] = list[j+1];
					list[j+1] = temp;
					swap = true;
				}
			}
			System.out.println(i+"\t"+ArrayUtils.toString(list));
			if(!swap){//没有交换任何数据
				break;
			}
		}
	}
	
	/**
	 * 冒泡排序改进版：添加下标，标记上一次发生数据交换的加标位置
	 * @param list
	 */
	public static void sortBetterIndex(int[] list){
		if(list == null || list.length == 0) return ;
		int temp;
		/**
		 * 1. 外层循环n次，代表要找n次最大值（右侧为最大值）
		 * 2. 内层循环n-i-1次，因为右侧已经为排序好的数据
		 */
		int index = list.length -1;
		int count = 0;
		while (index > 0) {
			int pos = 0;
			for (int j = 0; j < index; j++) {
				if(list[j]>list[j+1]){
					temp = list[j];
					list[j] = list[j+1];
					list[j+1] = temp;
					pos = j;
				}
			}
			index = pos;
			count++;
			System.out.println(count+"\t"+ArrayUtils.toString(list));
		}
	}
}
